package com.learn.algorithm_54;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * 54. 螺旋矩阵
 * https://leetcode-cn.com/problems/spiral-matrix/
 *
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * -100 <= matrix[i][j] <= 100
 *
 * @author gatts, 2022/1/20 19:54
 */
public class SpiralMatrix {

    @Test
    public void test() {
        int[][] matrix = {{1,2,3},{4,5,6},{7,8,9}};
        System.out.println(spiralOrder(matrix));
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        // 判断矩阵的长、宽
        int yMax = matrix.length;
        int xMax = matrix[0].length;
        // 矩阵元素个数
        int count = xMax * yMax;
        // 初始方向，向右
        int direction = 1;
        int y = 0;
        int x = 0;

        // 遍历矩阵所有元素，遍历过的元素置为999，不在矩阵元素取值范围即可
        for (; count > 0; count--) {
            // 向右遍历
            if (direction == 1) {
                if (x < xMax && matrix[y][x] != 999) {
                    result.add(matrix[y][x]);
                    matrix[y][x] = 999;
                    x++;
                }
                else {
                    x--; // 补偿上一次循环操作的++
                    count++; // 补偿count的本次循环，没取到值，浪费了，加回去
                    y++; // 为下次做准备，此时横向遍历到尾部，y要+1，从下一行开始
                    direction = 2; // 改变方向
                }

            }
            // 向下遍历
            else if (direction == 2) {
                if (y < yMax && matrix[y][x] != 999) {
                    result.add(matrix[y][x]);
                    matrix[y][x] = 999;
                    y++;
                }
                else {
                    y--;
                    count++;
                    x--;
                    direction = 3;
                }
            }
            // 向左遍历
            else if (direction == 3) {
                if (x >= 0 && matrix[y][x] != 999) {
                    result.add(matrix[y][x]);
                    matrix[y][x] = 999;
                    x--;
                }
                else {
                    x++;
                    count++;
                    y--;
                    direction = 4;
                }
            }
            // 向上遍历
            else if (direction == 4) {
                if (y >= 0 && matrix[y][x] != 999) {
                    result.add(matrix[y][x]);
                    matrix[y][x] = 999;
                    y--;
                }
                else {
                    y++;
                    count++;
                    x++;
                    direction = 1;
                }
            }
        }
        return result;
    }

}
